package com.dong.algorithm.novice.introduction;

import java.util.Arrays;

/**
 * sum(arr, L, R)的两种预处理设计
 * 1. 建一个正方形的二维数组
 *     （查的快，建二维表代价较大，n平方/2的空间）
 * 2. 前缀和数据（一维数组）
 *
 * 一般来看，从生成help数组的时间和空间上都是第一种方案更优；
 * 但是当查询量巨多，查询的数量级远大于数据的量级时，则生成help数组的代价可忽略，这时第一种方案更优，因为他查的更快
 *
 * @author by jiweidong on 2021/11/19.
 */
public class Alg02_ArrayRangeSum {

    public static void main(String[] args) {
        int arr[] = {3, 2, 9, 1, 0, 6, 2, 7};
        RangeSum1 rangeSum1 = new RangeSum1(arr);
        int result = rangeSum1.rangeSum(2, 5);
        System.out.println("result=" + result);

        RangeSum2 rangeSum2 = new RangeSum2(arr);
        int result2 = rangeSum2.rangeSum(2, 5);
        System.out.println("result2=" + result2);
    }

    public static class RangeSum1 {

        private int[][] preSum;

        public RangeSum1(int[] arr) {
            System.out.println("arr=" + Arrays.toString(arr));
            int N = arr.length;
            preSum = new int[N][N];
            for (int l = 0; l < N; l++) {
                preSum[l][l] = arr[l];
                for (int r = l + 1; r < N; r++) {
                    preSum[l][r] = preSum[l][r - 1] + arr[r];
                }
            }

            System.out.println("preSum1======");
            for (int i = 0; i < preSum.length; i++) {
                System.out.println(Arrays.toString(preSum[i]));
            }
        }

        public int rangeSum(int L, int R) {
            return preSum[L][R];
        }
    }

    public static class RangeSum2 {

        private int[] preSum;

        public RangeSum2(int[] arr) {
            System.out.println("arr=" + Arrays.toString(arr));
            int N = arr.length;
            preSum = new int[N];
            preSum[0] = arr[0];
            for (int i = 1; i < N; i++) {
                preSum[i] = preSum[i - 1] + arr[i];
            }
            System.out.println("preSum2=" + Arrays.toString(preSum));
        }

        public int rangeSum(int L, int R) {
            return L == 0 ? preSum[0] : preSum[R] - preSum[L - 1];
        }
    }


}
